1. Field of the Invention
This invention relates generally to halftone images, and more particularly to methods of generating dither arrays for use with output devices having sub-pixel addressability. The techniques may be implemented in an apparatus, as methods, or as programs of instructions for directing an apparatus or machine to carry out the processing steps of these techniques.
2. Description of the Related Art
Many image rendering technologies, referred to generally herein as output devices, have only binary outputs with respect to any one particular element or pixel, whereby each pixel of the image either has a dot printed or not printed. Input or source images, however, may have a gray scale of much greater depth, most typically 256 different tones (0 through 255) defined by 8 bits associated with each pixel. Thus, for an output device to render a gray scale image, it is necessary therefore to convert source images comprised of higher order gray levels into halftone images.
(A pixel is just one location on the addressable grid, whereas a dot generally refers to a physical positive rendering or inking which can be composed of any number of contiguous pixels, meaning one, two or more contiguous (or closely proximate) pixels form a single dot. In order to avoid confusion and assist the reader in more fully appreciating the present invention, in the present description “pixel” or “sub-pixel” and similar terms such as “grid” will be used to refer to the addressable locations; whereas “pixel-dot” will refer to a single printed or turned on pixel and “dot” will be used in referring to printed clusters of more than one pixel.)
The problem of representing gray scale images on a binary output device is known as “dithering” or “halftoning.” Halftoning creates the illusion of continuous tone images by judicious arrangement of binary picture elements, simulating the continuous tone image. Dithering relies on the fact that the human visual system integrates information over spatial regions, so that a pattern of light and dark evoke a sensation approximating that of a uniform gray area even when the individual display element can be resolved. In other words, it is the human eye that averages out these dots and creates a grayscale. Effective digital halftoning or dithering can substantially improve the quality of rendering images.
There are many known methods for halftoning, one of which is known as screening. The simplest form of screen is a single threshold value such as 128, and in applying this threshold to the original image a comparison is made with each pixel such that anything above 128 is set to 1 and anything below is set to zero. (Though purely a matter of convention, for the purposes of this description, a “1” represents a printing or existence of a dot in the binary halftone, and “0” represent an empty or omitted dot). However, basic single-level thresholding is prone to graininess and other deficiencies and generally does not create a very pleasing image in comparison to other methods.
Since basic thresholding techniques were first developed, many improved and alternate methods have been designed. One method transforms a gray scale image to a halftone image by means of a dither matrix. The dither matrix occupies a physical space and has numerous elements, each with an individual value. The dither matrix is mapped over the image to generate the halftone by a comparison of each pixel with the dither matrix value which overlays it. For a gray scale image that is larger than the dither matrix, the dither matrix is replicated or tiled to cover the entire image. As a result, the halftone image created has the same number of gray level patterns as the number of gray levels in the gray scale image. A darker area in the gray scale image is represented in the halftone image by gray patterns with more dots.
In order to generate a halftone images using the above method, the dither matrix must be carefully designed: a fully random pattern would create a halftone image that is noisy, corrupting the content of the image. Accordingly, the values associated with each pixel or address of the dither matrix are assigned specific thresholding values associated with the desired ordering and location in which pixels will be turned “on” as tone is added from one gray level to the next.
One prior art method of designing a dither matrix is known as the void-and-cluster method. A general discussion of this method can be found in “The Void and Cluster Method for Dither Array Generation” by Robert Ulichney, published in IS&T/SPIE Symposium on Electronic Imaging: Science and Technology, San Jose, Calif., 1993.
Another method of generating dither patterns or “screens” is found in “Perception of binary texture and the generation of halftone stochastic screens” by J. Dalton, published in IS&T/SPIE 1995 International Symposium on Electronic Imaging: Science and Technology, San Jose. Calif., 1995.
Another dither matrix approach is described in U.S. Pat. No. 5,317,418, “Halftone Images Using Special Filters” which is incorporated by reference herein. This approach, stochastic in nature, produces scattered dots resulting in very uniform patterns in the absence of dot-to-dot interactions in the printing engine.
Also, yet another variety of filtering to produce dither patterns and related matrixes is described in U.S. Pat. No. 6,335,989, “Halftone Printing Using Donut Filters”, which is also incorporated by reference herein.
However, one shortcoming common to conventional dithering techniques is that they are designed to operate on a pixel grid having substantially symmetric resolution. Certain output devices have a degree of sub-pixel addressability that provides an additional degree of resolution, typically greater in one direction of the pixel grid than the other. For instance, some laser printers may have a horizontal sub-pixel resolution of 2, 3 or more sub-pixels of resolution or addressability for every pixel. Accordingly, for known methods of halftoning developed to operate on a substantially symmetric grid design, use of sub-pixels can create problems and/or, most notably, the benefits of higher resolution attendant to sub-pixels are not fully recognized.
One advantage of using addressable sub-pixels in rendering halftone images is that it allows the addition of tone to be distributed among multiple other pixels or dot clusters. For example, an output device without sub-pixel addressability (or having it but unable to utilize it without a method of generating halftones for controlling the distribution of the sub-pixels) would be limited to applying additional tone by adding single whole pixels at a time. Conversely, the ability to address sub-pixels has the advantage of allowing the addition (or deletion) of tone from one graylevel to the next such that tone of even a single pixel dot value can be distributed among multiple other pixels or dot clusters.
What is needed is a technique that enables the design of dither matrices for creating half tone images that can take advantage of sub-pixel addressability of certain output devices, even in circumstances where the sub-pixel resolution is asymmetric. Moreover, and particularly desirable, is a solution allowing for the use of sub-pixel resolution using known or conventional dither matrix design methods that work on symmetric grids; thus, a solution having a way of applying such known methods to the asymmetric grids inherent of sub-pixels.